<?xml version="1.0" encoding="UTF-8" standalone="no"?>
<!DOCTYPE html><html xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" xmlns:m="http://www.w3.org/1998/Math/MathML" xmlns:pls="http://www.w3.org/2005/01/pronunciation-lexicon" xmlns:ssml="http://www.w3.org/2001/10/synthesis" xmlns:svg="http://www.w3.org/2000/svg">
  <head>
    <title>Lazy evaluation</title>
    <link rel="stylesheet" type="text/css" href="docbook-epub.css"/>
    <link rel="stylesheet" type="text/css" href="kawa.css"/>
    <script src="kawa-ebook.js" type="text/javascript"/>
    <meta name="generator" content="DocBook XSL-NS Stylesheets V1.79.1"/>
    <link rel="prev" href="Local-binding-constructs.xhtml" title="Local binding constructs"/>
    <link rel="next" href="Threads.xhtml" title="Threads"/>
  </head>
  <body>
    <header/>
    <section class="sect1" title="Lazy evaluation" epub:type="subchapter" id="Lazy-evaluation">
      <div class="titlepage">
        <div>
          <div>
            <h2 class="title" style="clear: both">Lazy evaluation</h2>
          </div>
        </div>
      </div>
      <p><em class="firstterm">Lazy evaluation</em> (or call-by-need) delays evaluating an expression until it
is actually needed; when it is evaluated, the result is saved so
repeated evaluation is not needed.
<a class="ulink" href="http://en.wikipedia.org/wiki/Lazy_evaluation" target="_top">Lazy evaluation</a>
is a technique that can make some algorithms easier to express compactly
or much more efficiently, or both.  It is the normal evaluation mechanism
for strict functional (side-effect-free) languages such as
<a class="ulink" href="http://www.haskell.org" target="_top">Haskell</a>.
However, automatic lazy evaluation is awkward to combine with side-effects
such as input-output.  It can also be difficult to implement
lazy evaluation efficiently, as it requires more book-keeping.
</p>
      <p>Kawa, like other Schemes, uses “eager evaluation” - an expression
is normally evaluated immediately, unless it is wrapped in a special form.
Standard Scheme has some basic building blocks for “manual”
lazy evaluation, using an explicit <code class="literal">delay</code> operator to
indicate that an expression is to be evaluated lazily,
yielding a <em class="firstterm">promise</em>,
and a <code class="literal">force</code> function to force evaluation of a promise.
This functionality is enhanced in
<a class="ulink" href="http://srfi.schemers.org/srfi-45/srfi-45.html" target="_top">SRFI 45</a>,
in R7RS-draft (based on SRFI 45),
and <a class="ulink" href="http://srfi.schemers.org/srfi-41/srfi-41.html" target="_top">SRFI 41</a> (lazy lists aka streams).
</p>
      <p>Kawa makes lazy evaluation easier to use, by <em class="firstterm">implicit forcing</em>:
The promise is automatically evaluated (forced) when used in a
context that requires a normal value, such as arithmetic needing a number.
Kawa enhances lazy evaluation in other ways, including
support for safe multi-threaded programming.
</p>
      <section class="sect2" title="Delayed evaluation" epub:type="division" id="idm139667878104384">
        <div class="titlepage">
          <div>
            <div>
              <h3 class="title">Delayed evaluation</h3>
            </div>
          </div>
        </div>
        <p class="synopsis" kind="Syntax"><span class="kind">Syntax</span><span class="ignore">: </span><a id="idm139667878103312" class="indexterm"/> <code class="function">delay</code> <em class="replaceable"><code><a class="link" href="Primitive-expression-syntax.xhtml#meta-expression"><em class="replaceable"><code>expression</code></em></a></code></em></p>
        <div class="blockquote">
          <blockquote class="blockquote">
            <p>The <code class="literal">delay</code> construct is used together with the procedure
<code class="literal">force</code> to implement <span class="emphasis"><em>lazy evaluation</em></span> or <span class="emphasis"><em>call by need</em></span>.
</p>
            <p>The result of <code class="literal">(delay <em class="replaceable"><code>expression</code></em>)</code> is a
<span class="emphasis"><em>promise</em></span> which at some point in the future may be asked (by the
<code class="literal">force</code> procedure) to evaluate <em class="replaceable"><code>expression</code></em>, and deliver the
resulting value.  The effect of <em class="replaceable"><code>expression</code></em> returning multiple
values is unspecified.
</p>
          </blockquote>
        </div>
        <p class="synopsis" kind="Syntax"><span class="kind">Syntax</span><span class="ignore">: </span><a id="idm139667878094416" class="indexterm"/> <code class="function">delay-force</code> <em class="replaceable"><code><a class="link" href="Primitive-expression-syntax.xhtml#meta-expression"><em class="replaceable"><code>expression</code></em></a></code></em></p>
        <p class="synopsis" kind="Syntax"><span class="kind">Syntax</span><span class="ignore">: </span><a id="idm139667878091056" class="indexterm"/> <code class="function">lazy</code> <em class="replaceable"><code><a class="link" href="Primitive-expression-syntax.xhtml#meta-expression"><em class="replaceable"><code>expression</code></em></a></code></em></p>
        <div class="blockquote">
          <blockquote class="blockquote">
            <p>The <code class="literal">delay-force</code> construct is similar to <code class="literal">delay</code>, but it is expected
that its argument evaluates to a promise.
(Kawa treats a non-promise value as if it were a forced promise.)
The returned
promise, when forced, will evaluate to whatever the original
promise would have evaluated to if it had been forced.
</p>
            <p>The expression <code class="literal">(delay-force <em class="replaceable"><code>expression</code></em>)</code> is
conceptually similar to <code class="literal">(delay (force <em class="replaceable"><code>expression</code></em>))</code>, with
the difference that forcing the result of <code class="literal">delay-force</code> will
in effect result in a tail call to <code class="literal">(force <em class="replaceable"><code>expression</code></em>)</code>, while
forcing the result of <code class="literal">(delay (force <em class="replaceable"><code>expression</code></em>))</code> might
not. Thus iterative lazy algorithms that might result in a
long series of chains of <code class="literal">delay</code> and <code class="literal">force</code> can be rewritten
using delay-force to prevent consuming unbounded space
during evaluation.
</p>
            <p>Using <code class="literal">delay-force</code> or <code class="literal">lazy</code> is equivalent.
The name <code class="literal">delay-force</code> is from R7RS; the name <code class="literal">lazy</code>
is from the older SRFI-45.
</p>
          </blockquote>
        </div>
        <p class="synopsis" kind="Procedure"><span class="kind">Procedure</span><span class="ignore">: </span><a id="idm139667878078272" class="indexterm"/> <code class="function">eager</code> <em class="replaceable"><code>obj</code></em></p>
        <div class="blockquote">
          <blockquote class="blockquote">
            <p>Returns a promise that when forced will return <em class="replaceable"><code>obj</code></em>.
It is similar to <code class="literal">delay</code>, but does not delay its argument;
it is a procedure rather than syntax.
</p>
            <p>The Kawa implementation just returns <em class="replaceable"><code>obj</code></em> as-is.
This is because Kawa treats as equivalent
a value and forced promise evaluating to the value.
</p>
          </blockquote>
        </div>
        <p class="synopsis" kind="Procedure"><span class="kind">Procedure</span><span class="ignore">: </span><a id="idm139667878073040" class="indexterm"/> <code class="function">force</code> <em class="replaceable"><code>promise</code></em></p>
        <div class="blockquote">
          <blockquote class="blockquote">
            <p>The <code class="literal">force</code> procedure forces the value of <em class="replaceable"><code>promise</code></em>.
As a Kawa extension, if the <em class="replaceable"><code>promise</code></em> is not a promise (a value that
does not implement <code class="literal">gnu.mapping.Lazy</code>) then the argument is returned unchanged.
If no value has been computed for the promise, then a value is computed and
returned.  The value of the promise is cached (or “memoized”) so that
if it is forced a second time, the previously computed value is
returned.
</p>
            <pre class="screen">(force (delay (+ 1 2)))                ⇒  3

(let ((p (delay (+ 1 2))))
  (list (force p) (force p)))          ⇒  (3 3)

(define integers
  (letrec ((next
            (lambda (n)
              (cons n (delay (next (+ n 1)))))))
    (next 0)))
(define head 
  (lambda (stream) (car (force stream)))) 
(define tail 
  (lambda (stream) (cdr (force stream)))) 

(head (tail (tail integers)))          ⇒  2
</pre>
            <p>The following example is a mechanical transformation of
a lazy stream-filtering algorithm into Scheme. Each call
to a constructor is wrapped in <code class="literal">delay</code>, and each argument
passed to a deconstructor is wrapped in <code class="literal">force</code>. The use
of <code class="literal">(lazy ...)</code> instead of <code class="literal">(delay (force ...))</code> around
the body of the procedure ensures that an ever-growing
sequence of pending promises does not exhaust the heap.
</p>
            <pre class="screen">(define (stream-filter p? s)
  (lazy
   (if (null? (force s))
       (delay ’())
       (let ((h (car (force s)))
             (t (cdr (force s))))
         (if (p? h)
             (delay (cons h (stream-filter p? t)))
             (stream-filter p? t))))))

(head (tail (tail (stream-filter odd? integers))))
    ⇒ 5
</pre>
          </blockquote>
        </div>
        <p class="synopsis" kind="Procedure"><span class="kind">Procedure</span><span class="ignore">: </span><a id="idm139667878062352" class="indexterm"/> <code class="function">force*</code> <em class="replaceable"><code>promise</code></em></p>
        <div class="blockquote">
          <blockquote class="blockquote">
            <p>Does <code class="literal">force</code> as many times as necessary to produce a non-promise.
(A non-promise is a value that does not implement <code class="literal">gnu.mapping.Lazy</code>,
or if it does implement <code class="literal">gnu.mapping.Lazy</code> then forcing the value
using the <code class="literal">getValue</code> method yields the receiver.)
</p>
            <p>The <code class="literal">force*</code> function is a Kawa extension.
Kawa will add implicit calls to <code class="literal">force*</code>
in most contexts that need it, but you can also call it explicitly.
</p>
          </blockquote>
        </div>
        <p>The following examples are not intended to illustrate good
programming style, as <code class="literal">delay</code>, <code class="literal">lazy</code>, and <code class="literal">force</code> are mainly
intended for programs written in the functional style.
However, they do illustrate the property that only one value is
computed for a promise, no matter how many times it is
forced.
</p>
        <pre class="screen">(define count 0)
(define p
  (delay (begin (set! count (+ count 1))
                (if (&gt; count x)
                    count
                    (force p)))))
(define x 5)
p                  ⇒ <span class="emphasis"><em>a promise</em></span>
(force p)          ⇒ 6
p                  ⇒ <span class="emphasis"><em>a promise, still</em></span>
(begin (set! x 10)
       (force p))  ⇒ 6
</pre>
      </section>
      <section class="sect2" title="Implicit forcing" epub:type="division" id="idm139667878051664">
        <div class="titlepage">
          <div>
            <div>
              <h3 class="title">Implicit forcing</h3>
            </div>
          </div>
        </div>
        <p>If you pass a promise as an argument to a function like <code class="literal">sqrt</code>
if must first be forced to a number.  In general, Kawa does this
automatically (implicitly) as needed, depending on the context.
For example:
</p>
        <pre class="screen">(+ (delay (* 3 7)) 13)   ⇒ 34
</pre>
        <p>Other functions,
like <code class="literal">cons</code> have no problems with promises, and automatic forcing
would be undesirable.
</p>
        <p>Generally, implicit forcing happens for arguments that require a
specific type, and does not happen for arguments that work on
<span class="emphasis"><em>any</em></span> type (or <code class="literal">Object</code>).
</p>
        <p>Implicit forcing happens for:
</p>
        <div class="itemizedlist" epub:type="list">
          <ul class="itemizedlist" style="list-style-type: disc; ">
            <li class="listitem" epub:type="list-item">
              <p>arguments to arithmetic functions;
</p>
            </li>
            <li class="listitem" epub:type="list-item">
              <p>the sequence and the index in indexing operations, like <code class="literal">string-ref</code>;
</p>
            </li>
            <li class="listitem" epub:type="list-item">
              <p>the operands to <code class="literal">eqv?</code> and <code class="literal">equal?</code> are forced,
though the operands to <code class="literal">eq?</code> are not;
</p>
            </li>
            <li class="listitem" epub:type="list-item">
              <p>port operands to port functions;
</p>
            </li>
            <li class="listitem" epub:type="list-item">
              <p>the value to be emitted by a <code class="literal">display</code> but <span class="emphasis"><em>not</em></span> the
value to be emitted by a <code class="literal">write</code>;
</p>
            </li>
            <li class="listitem" epub:type="list-item">
              <p>the function in an application.
</p>
            </li>
          </ul>
        </div>
        <p>Type membership tests, such as the <code class="literal">instance?</code> operation,
generally do not force their values.
</p>
        <p>The exact behavior for when implicit forcing happens is a work-in-progress:
There are certainly places where implicit forcing doesn’t happen while
it should; there are also likely to be places where implicit forcing
happens while it is undesirable.
</p>
        <p>Most Scheme implementations are such that a forced promise behaves differently
from its forced value, but some Scheme implementions are such that there is no
means by which a promise can be operationally distinguished
from its forced value.
Kawa is a hybrid: Kawa tries to minimize the difference between
a forced promise and its forced value, and may freely optimize
and replace a forced promise with its value.
</p>
      </section>
      <section class="sect2" title="Blank promises" epub:type="division" id="idm139667878038224">
        <div class="titlepage">
          <div>
            <div>
              <h3 class="title">Blank promises</h3>
            </div>
          </div>
        </div>
        <p>A <em class="firstterm">blank promise</em> is a promise that doesn’t (yet) have
a value <span class="emphasis"><em>or</em></span> a rule for calculating the value.
Forcing a blank promise will wait forever, until some
other thread makes the promise non-blank.
</p>
        <p>Blank promises are useful as a synchronization mechanism -
you can use it to safely pass data from one thread (the producer)
to another thread (the consumer).  Note that you can only
pass one value for a given promise: To pass multiple values, you
need multiple promises.
</p>
        <pre class="screen">(define p (promise))
(future ;; Consumer thread
  (begin
    (do-stuff)
    (define v (force promise)) ; waits until promise-set-value!
    (do-stuff-with v)))
;; Producer thread
... do stuff ...
(promise-set-value! p (calculate-value))
</pre>
        <p class="synopsis" kind="Constructor"><span class="kind">Constructor</span><span class="ignore">: </span><a id="idm139667878034448" class="indexterm"/> <code class="function">promise</code></p>
        <div class="blockquote">
          <blockquote class="blockquote">
            <p>Calling <code class="literal">promise</code> as a zero-argument constructor
creates a new blank promise.
</p>
            <p>This calls the constructor for <code class="literal">gnu.mapping.Promise</code>.
You can also create a non-blank promise, by setting one
of the <code class="literal">value</code>, <code class="literal">alias</code>, <code class="literal">thunk</code>, or <code class="literal">exception</code> properties.
Doing so is equivalent to calling <code class="literal">promise-set-value!</code>,
<code class="literal">promise-set-alias!</code>, <code class="literal">promise-set-thunk!</code>, or
<code class="literal">promise-set-exception!</code> on the resulting promise.
For example: <code class="literal">(delay exp)</code> is equivalent to:
</p>
            <pre class="screen">(promise thunk: (lambda() exp))
</pre>
          </blockquote>
        </div>
        <p>The following four procedures require that their first arguments
be blank promises.  When the procedure returns, the promise is
no longer blank, and cannot be changed.  This is because a
promise is conceptually a placeholder for a single “not-yet-known” value;
it is not a location that can be assigned multiple times.
The former enables clean and safe (“declarative") use of multiple threads;
the latter is much trickier.
</p>
        <p class="synopsis" kind="Procedure"><span class="kind">Procedure</span><span class="ignore">: </span><a id="idm139667878024912" class="indexterm"/> <code class="function">promise-set-value!</code> <em class="replaceable"><code>promise</code></em> <em class="replaceable"><code>value</code></em></p>
        <div class="blockquote">
          <blockquote class="blockquote">
            <p>Sets the value of the <em class="replaceable"><code>promise</code></em> to <em class="replaceable"><code>value</code></em>,
which makes the <em class="replaceable"><code>promise</code></em> forced.
</p>
          </blockquote>
        </div>
        <p class="synopsis" kind="Procedure"><span class="kind">Procedure</span><span class="ignore">: </span><a id="idm139667878019776" class="indexterm"/> <code class="function">promise-set-exception!</code> <em class="replaceable"><code>promise</code></em> <em class="replaceable"><code>exception</code></em></p>
        <div class="blockquote">
          <blockquote class="blockquote">
            <p>Associate <em class="replaceable"><code>exception</code></em> with the <em class="replaceable"><code>promise</code></em>.
When the <em class="replaceable"><code>promise</code></em> is forced the <em class="replaceable"><code>exception</code></em> gets thrown.
</p>
          </blockquote>
        </div>
        <p class="synopsis" kind="Procedure"><span class="kind">Procedure</span><span class="ignore">: </span><a id="idm139667878014192" class="indexterm"/> <code class="function">promise-set-alias!</code> <em class="replaceable"><code>promise</code></em> <em class="replaceable"><code>other</code></em></p>
        <div class="blockquote">
          <blockquote class="blockquote">
            <p>Bind the <em class="replaceable"><code>promise</code></em> to be an alias of <em class="replaceable"><code>other</code></em>.
Forcing <em class="replaceable"><code>promise</code></em> will cause <em class="replaceable"><code>other</code></em> to be forced.
</p>
          </blockquote>
        </div>
        <p class="synopsis" kind="Procedure"><span class="kind">Procedure</span><span class="ignore">: </span><a id="idm139667878008608" class="indexterm"/> <code class="function">promise-set-thunk!</code> <em class="replaceable"><code>promise</code></em> <em class="replaceable"><code>thunk</code></em></p>
        <div class="blockquote">
          <blockquote class="blockquote">
            <p>Associate <em class="replaceable"><code>thunk</code></em> (a zero-argument procedure) with the <em class="replaceable"><code>promise</code></em>.
The first time the <em class="replaceable"><code>promise</code></em> is forced will causes the
<em class="replaceable"><code>thunk</code></em> to be called, with the result (a value or an exception)
saved for future calls.
</p>
          </blockquote>
        </div>
        <p class="synopsis" kind="Procedure"><span class="kind">Procedure</span><span class="ignore">: </span><a id="idm139667878002928" class="indexterm"/> <code class="function">make-promise</code> <em class="replaceable"><code>obj</code></em></p>
        <div class="blockquote">
          <blockquote class="blockquote">
            <p>The <code class="literal">make-promise</code> procedure returns a promise which,
when forced, will return <em class="replaceable"><code>obj</code></em>. It is similar to <code class="literal">delay</code>, but
does not delay its argument: it is a procedure rather than
syntax. If <em class="replaceable"><code>obj</code></em> is already a promise, it is returned.
</p>
            <p>Because of Kawa’s implicit forcing, there is seldom a
need to use <code class="literal">make-promise</code>, except for portability.
</p>
          </blockquote>
        </div>
      </section>
      <section class="sect2" title="Lazy and eager types" epub:type="division" id="idm139667877996688">
        <div class="titlepage">
          <div>
            <div>
              <h3 class="title">Lazy and eager types</h3>
            </div>
          </div>
        </div>
        <p class="synopsis" kind="Type"><span class="kind">Type</span><span class="ignore">: </span><a id="idm139667877995616" class="indexterm"/> <code class="function">promise[T]</code></p>
        <div class="blockquote">
          <blockquote class="blockquote">
            <p>This parameterized type is the type of promises that evaluate to
an value of type <code class="literal">T</code>.
It is equivalent to the Java interface <code class="literal">gnu.mapping.Lazy&lt;T&gt;</code>.
The implementation class for promises is usually <code class="literal">gnu.mapping.Promise</code>,
though there are other classes that implement <code class="literal">Lazy</code>,
most notably <code class="literal">gnu.mapping.Future</code>, used for futures,
which are promises evaluated in a separate thread.
</p>
          </blockquote>
        </div>
        <p>Note the distinction between the types <code class="literal">integer</code>
(the type of actual (eager) integer values), and <code class="literal">promise[integer]</code>
(the type of (lazy) promises that evaluate to integer).
The two are compatible: if a <code class="literal">promise[integer]</code> value is provided
in a context requiring an <code class="literal">integer</code> then it is automatically
evaluated (forced).  If an <code class="literal">integer</code> value is provided
in context requiring a <code class="literal">promise[integer]</code>, that conversion is basically
a no-op (though the compiler may wrap the <code class="literal">integer</code>
in a pre-forced promise).
</p>
        <p>In a fully-lazy language there would be no distinction, or
at least the promise type would be the default.  However, Kawa is
a mostly-eager language, so the eager type is the default.
This makes efficient code-generation easier: If an expression
has an eager type, then the compiler can generate code that
works on its values directly, without having to check for laziness.
</p>
      </section>
    </section>
    <footer>
      <div class="navfooter">
        <ul>
          <li>
            <b class="toc">
              <a href="Lazy-evaluation.xhtml#idm139667878104384">Delayed evaluation</a>
            </b>
          </li>
          <li>
            <b class="toc">
              <a href="Lazy-evaluation.xhtml#idm139667878051664">Implicit forcing</a>
            </b>
          </li>
          <li>
            <b class="toc">
              <a href="Lazy-evaluation.xhtml#idm139667878038224">Blank promises</a>
            </b>
          </li>
          <li>
            <b class="toc">
              <a href="Lazy-evaluation.xhtml#idm139667877996688">Lazy and eager types</a>
            </b>
          </li>
        </ul>
        <p>
          Up: <a accesskey="u" href="Program-structure.xhtml">Program structure</a></p>
        <p>
        Previous: <a accesskey="p" href="Local-binding-constructs.xhtml">Local binding constructs</a></p>
        <p>
        Next: <a accesskey="n" href="Threads.xhtml">Threads</a></p>
      </div>
    </footer>
  </body>
</html>
